Field of the Invention
The present invention generally relates to time critical Location Based Service (LBS) applications in mobile ad-hoc networks and, more particularly, to a platform for self-organized networking systems localization.
Background Description
The success of an LBS application depends on two pipelined procedures: localization of a device and information transmission. The localization problem has been extensively studied under a number of contexts such as wireless sensor networks, mobile ad-hoc networks (MANETs), and IEEE 802.11 wireless networks. Under the conventional localization definition, localizing both the source and the destination devices in the same co-ordinate system is a necessary condition to start the information transmission of an LBS application.
The conventional localization procedure, initiated from a few anchors, propagates the localization information to all users via flooding. As a result, the localization time is bounded below roughly by Tmin(rh, t1, k) defined by the following formula:Tmin(rht1,k)=(k×rh)×(t1+ΔD),  (1)where rh is the radius of the network in the form of the number of hops, t1 is the time needed for localizing one user (including the processes of direct neighborhood discovery, distance measurement, and trilateration, k is a parameter related to the positions of anchors, and ΔD is the average transmission delay at each user.
For a typical network setup with three anchors deployed in the center of a network, we have k=1, where Tmin(rh, t1, k) is the minimum time for transmitting a message from a user in the center to a user on the border. The localization time Tmin(rh, t1, 1) is also the lower bound for relative localization where each user starts localization by constructing a Local Coordinate System (LCS) itself. The reason is that the conventional localization definition requires that all the users be localized in the same coordinate system. In other words, the positions of the users under their own LCSs need to be transformed to the global coordinate system, and the position transformations also need to propagate information across the entire network.
Consequently, an LBS application has to wait for at least Tmin time before transmitting information. While Tmin may be suitable for time-critical LBS applications in static networks, where the localization procedure only needs to be conducted once, it may not be good for those in MANETs, whose network topology may have changed dramatically during the Tmin time frame, preventing the conventional localization procedure from localizing all users in the same co-ordinate system. As a result, LBS applications could fail because information transmission cannot start, which may also cause excessive amount of energy consumption because the localization process usually keeps trying to localize all the users in a network. Even if the source can eventually obtain a position of the destination, this position may be an old one that is far away from the current position of the destination. Therefore, the convention localization techniques cannot be directly applied to time-critical LBS applications in MANETs.
Deploying a large number anchors is a simple solution, with the purpose that every spot in the network can be covered by three non-collinear, or four non-coplane, anchors for two-dimensional (2D), or three-dimensional (3D) localization. Another solution is to equip every user with a Global Position System (GPS) receiver. These two solutions, however, may not be practical for the following reasons: (1) Deploying a large number of anchors may be impossible, or uneconomical, even if deployment is not an issue. (2) the GPS satellites may be destroyed or interfered by opponents in a battle field. (3) Not all the users always turn on their GPS receivers.